package com.example.algorithm.dynamicprogramming;

import com.example.tree.TreeNode;

/**
 * 给定一个二叉树，我们在树的节点上安装摄像头。
 * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
 * 计算监控树的所有节点所需的最小摄像头数量。
 * <p>
 * 示例 1：
 * 输入：[0,0,null,0,0]
 * 输出：1
 * <p>
 * 示例 2：
 * 输入：[0,0,null,0,null,0,null,null,0]
 * 输出：2
 * <p>
 * 提示：
 * 给定树的节点数的范围是 [1, 1000]。
 * 每个节点的值都是 0。
 */
public class Leetcode968_MinCameraCover {
    public static void main(String[] args) {
        // [0,0,null,0,0]
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(0);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(0);

        System.out.println(new Solution().minCameraCover(root));

    }

    static class Solution {

        /**
         * 动态规划
         * 暴力法任一个节点都会遍历它的左右子树的节点，产生了很多重复遍历
         *
         * 本题需要将摄像头按在叶子节点的父节点上，这样摄像头才是最少的
         * 这需要知道树左右子节点的状态,因此使用后序遍历会更好
         *
         * 1.子问题:
         *   每个子树能被监控所需的最少摄像头个数
         *
         * 2.状态
         * 对于每个节点有如下三种状态
         *   该节点无覆盖，用0表示
         *   该节点放置摄像头，用1表示 (该节点没有摄像头= 无覆盖or 有覆盖)
         *   该节点有覆盖，用2表示
         *
         * 3.状态转移方程:
         *   根据左右子节点推出根节点的状态
         *     1.左右子节点为有覆盖
         *     2.左右子节点至少有一个为无覆盖
         *
         * @param root
         * @return
         */
        // 定义三种状态
        private final int NOT_COVERED = 0;
        private final int HAS_CAMERA = 1;
        private final int CVERED = 2;
        int res = 0;// 表示所需要的摄像头的数量
        public int minCameraCover2(TreeNode root) {
            if (root == null) {
                return 0;
            }
            if (afterTraversal(root) == NOT_COVERED) { // 边界条件 根节点无覆盖,则摄像头数要加1
                res++;
            }

            return res;
        }

        /**
         * 后序遍历，返回根节点的状态
         * @param root
         * @return 根节点的状态
         */
        private int afterTraversal(TreeNode root) {
            // 如果是空的，就不需要相机了
            if (root == null){ return CVERED; }//
            int leftState = afterTraversal(root.left);
            int rightState = afterTraversal(root.right);
            // 如果左右子节点有一个是NOT_COVERED，表示的是子节点既没相机，也没相机覆盖它，所以当前节点需要有一个相机
            if (leftState == NOT_COVERED || rightState == NOT_COVERED) {
                //在当前节点放一个相机，统计相机的个数
                res++;
                return HAS_CAMERA;
            }
            // 如果左右子节点只要有一个有相机，那么当前节点就不需要相机了，否则返回一个没有相机的标记
            return leftState == HAS_CAMERA || rightState == HAS_CAMERA ? CVERED : NOT_COVERED;
        }

        /**
         * 方法一:暴力搜索(超时)
         * 摄像头放到非叶子节点上监视的范围最大(父节点+左右子节点)
         * 任意一个节点是否放置摄像头取决于其父节点+左子节点+右子节点的状态
         * <p>
         * 从上往下(前序遍历)，依次搜索所有可能性，取最小
         * 放置摄像头的节点val=1,不放置val=0
         * 由于每个节点的状态受到上层节点的影响，搜索时候需要添加一个参数interval
         * <p>
         * interval=0 表示当前节点的父节点放置了摄像头
         * interval=1 表示当前节点的父节点的父节点放置了摄像头
         * internal=2 表示当前节点的父节点的父节点也未放置摄像头
         * <p>
         * 则当前节点为根节点的树所需最小摄像头取决于interval+左右子树的状态，需要分类讨论
         * 1.internal=2 该节点必须要放置摄像头才能进行监控
         * 2.internal=1
         * 2.1 internal=1 左右子节点都不存在
         * 该节点必须放置摄像头
         * 2.2 internal=1 左右子节点都存在
         * 可以将摄像头放在该节点也可以放在它的子节点(哪种需要的摄像头少,用哪种方案)
         * 3.internal=0
         * 该节点能被监控,因此可以不在再放置摄像头也可以在左右子节点再放置(哪种需要的摄像头少,用哪种方案)
         *
         * @param root
         * @return
         */
        public int minCameraCover1(TreeNode root) {
            if (root == null) {
                return 0;
            }

            // 根节点没有父节点不可能为0,根节点不一定非要放置摄像头,所以internal=1
            return beforeOrderTraversal(root, 1);
        }

        /**
         * 前序遍历找到能监控所有节点的最小摄像头数
         *
         * @param root
         * @param interval
         * @return
         */
        private int beforeOrderTraversal(TreeNode root, int interval) {
            if (root == null) return 0; // 递归出口

            if (interval == 1 && root.left == null && root.right == null) {// interval=1 左右子节点都不存在,该节点必须放置摄像头
                root.val = 1;
                return 1;
            }

            if (interval == 1 && root.left != null && root.right != null) {// 左右子节点都存在,摄像头可以放在左右子节点或者该节点上
                // 放在该节点上
                root.val = 1;
                int rootCount = beforeOrderTraversal(root.left, 0)
                        + beforeOrderTraversal(root.right, 0) + 1;

                root.val = 0; // 复原节点值
                int leftCount = beforeOrderTraversal(root.left, interval + 1)
                        + beforeOrderTraversal(root.right, interval); // 放在左子节点
                int rightCount = beforeOrderTraversal(root.left, interval)
                        + beforeOrderTraversal(root.right, interval + 1);// 放在右子节点上

                if (rootCount < Math.min(rightCount, leftCount)) {
                    return rootCount;
                } else {
                    return Math.min(rightCount, leftCount);
                }
            }

            if (interval == 2) { // interval=2,当前节点一定得放置摄像头
                root.val = 1;
                return beforeOrderTraversal(root.left, 0) + beforeOrderTraversal(root.right, 0) + 1;
            } else { // 其他情况统一处理
                // interval=0 或 interval=1但左右子树有一个为空
                root.val = 1;//放置此节点
                int x = beforeOrderTraversal(root.left, 0)
                        + beforeOrderTraversal(root.right, 0) + 1;
                root.val = 0;
                // 左右子树都放置(只有一个能放成功，因为必有一个为空)
                int y = beforeOrderTraversal(root.left, interval + 1) + beforeOrderTraversal(root.right, interval + 1);
                if(x < y){
                    root.val = 1;
                    return x;
                } else {
                    return y;
                }
            }

        }

        public int minCameraCover(TreeNode root) {
            return minCameraCover1(root);
        }
    }
}
